<html>
<head>
<title>The Cave</title>
</head>

<center>
<h1>CEOI 97 Day 1 Problem 1</h1>
<h1>The Cave</h1>
</center>

<p>
There is a lot of caves in Byteland. This is the map of one of them:
<p>
<center><img src="image/116.gif" border=0></center> 
</p>

<p> 
All caves in Byteland have the following properties:
<ul>
	<li>All the chambers and passages are on the same level.
	<li>No two passages cross each other.
	<li>Some of the chambers are situated on the outer circle.
	They are called outer chambers.
	<li>All the other chambers lie inside the outer circle and are
	called <b>inner chambers</b>.
	<li>There is an entrance to the cave leading to one of the <b>outer
	chambers</b>.
	<li>There are exactly three passages leading from every chamber
	to three different other chambers. If a chamber is an outer
	chamber then two of the passages lead to two neighbouring outer
	chambers on the circle and exactly one leads to an inner chamber.
	<li>Passages connecting outer chambers are called <b>outer passages</b>
	and the remaining ones are called <b>inner passages</b>.
	<li>It is possible to walk from one chamber to another using
	only inner passages but there is only one way to do that if we
	allow to walk through every inner passage at most once.
	<li>Not all passages are equally hard to go through. They are
	divided into two groups: easy and hard.
</ul>

<p>
It has been decided to open all the caves to the public. To assure
a "smooth" and safe flow through a cave, visitors should follow a
route marked in advance and visit every chamber of this cave exactly
once.
An exception from this rule is the entrance chamber where every tour
begins and ends, you are allowed to visit this chamber exactly
twice. The tour route should be fit for an average visitor and
contain as few hard passages to walk through as possible.

<h2>Example</h2>
Consider the cave showed in the figure. The entrance chamber is 1.
The dashed passages are hard to walk through.
Route 1, 5, 4, 6, 8, 7, 2, 3 contains no hard passages at all.
The final chamber, number 1, is implied and not listed.

<h2>Task</h2>
Write a program that:
<ul>
	<li>reads the description of a cave from the text file CAV.IN;
	<li>finds a route through the cave that begins and ends in the
	entrance chamber, lets the visitors see all the other chambers
	only once and contains as few hard passages as possible;
	<li>writes the result to the text file CAV.OUT	
</ul>

<h2>Input</h2>
There are two integers n, k (separated by a single space) in the
first line of the text file CAV.IN
The integer n, 3 &lt; n &lt;= 500, is the number of all chambers
in a cave and k is the number of all its outer chambers, k &gt;= 3.
The chambers are numbered from 1 to n. Chamber 1 is the entrance
chamber. Chambers 1, 2, ..., k are outer chambers.
They do not have to appear on the outer circle in this order.
<p>
The next 3n / 2 lines contain descriptions of the passages.
Each description consists of three integers a, b, c separated
by single spaces. The integers a and b are numbers of chambers
at the ends of a passage. The integer c equals 0 or 1, where 0
means that the passage is easy to walk through and 1 that it
is hard.

<h2>Output</h2>
Your program should write a sequence of n integers separated
by single spaces to the first line of the text file CAV.OUT;
the sequence has to begin with 1 (the entrance chamber). The
following n - 1 integers should be consecutive chambers on the
computed route.
<p>

<h2>Sample Input</h2>
<pre>
8 5
1 3 0
3 2 0
7 3 1
7 2 0
8 7 0
1 8 0
6 8 0
6 4 0
6 5 1
5 4 0
2 4 0
5 1 0
</pre>

<h2>Sample Output</h2>
<pre>
1 5 4 6 8 7 2 3
</pre>

</body>
</html>

